package com.example.arithmeticleetcode.leetcode.dec;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * @program: arithmetic-leetcode
 * @description: 相同的树
 * @author: FangZhen
 * @create: 2020-12-24 10:18
 **/
public class Demo24 {

    public static void main(String[] args) {
        Queue<TreeNode> pQuque = new LinkedList<>();
        pQuque.offer(null);
        System.out.println(pQuque.size());
    }

    public boolean isSameTree(TreeNode p, TreeNode q) {
        return isSameTree(p).equals(isSameTree(q));
    }

    public String isSameTree(TreeNode p) {
        if (p == null) return "";
        StringBuilder sb = new StringBuilder();
        isSameTree(p, sb);
        return sb.toString();
    }

    public void isSameTree(TreeNode p, StringBuilder sb) {
        if (p.left == null) {
            sb.append("left");
        } else {
            isSameTree(p.left, sb);
        }

        if (p.right == null) {
            sb.append("right");
        } else {
            isSameTree(p.right, sb);
        }
        sb.append(p.val).append("!");
    }

    public boolean kLengthApart(int[] nums, int k) {
        if (nums.length == 1) return true;
        List<Integer> list = new ArrayList<>();
        boolean headFlag = true, tailFlag = true;
        for (int i = 0, len = nums.length; i < len; i++) {
            if (nums[i] == 1) {
                list.add(i);
            }
        }
        int len = list.size();
        if (len == 1) return true;
        for (int i = 1; i < len; i++) {
            if (list.get(i) - list.get(i - 1) - 1 < k) return false;
        }
        return true;
    }

    public boolean isSameTree2(TreeNode p, TreeNode q) {
        if (p == null && q == null) return true;
        if (p == null || q == null) return false;
        if (p.val != q.val) return false;
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }


    public boolean isSameTree3(TreeNode p, TreeNode q) {
        if (p == null && q == null) return true;
        if (p == null || q == null) return false;
        Queue<TreeNode> queue1 = new LinkedList<>();
        Queue<TreeNode> queue2 = new LinkedList<>();
        queue1.offer(p);
        queue2.offer(q);
        while (!queue1.isEmpty() && !queue2.isEmpty()) {
            TreeNode treeNode1 = queue1.poll();
            TreeNode treeNode2 = queue2.poll();
            if (treeNode1.val != treeNode2.val) return false;
            TreeNode treeNode1Left = treeNode1.left, treeNode1Right = treeNode1.right, treeNode2Left = treeNode2.left, treeNode2Right = treeNode2.right;
            if (treeNode1Left == null ^ treeNode2Left == null) return false;
            if (treeNode1Right == null ^ treeNode2Right == null) return false;
            if (treeNode1Left != null) queue1.offer(treeNode1Left);
            if (treeNode1Right != null) queue1.offer(treeNode1Right);
            if (treeNode2Left != null) queue2.offer(treeNode2Left);
            if (treeNode2Right != null) queue2.offer(treeNode2Right);
        }
        return queue1.isEmpty() && queue2.isEmpty();
    }
}
